#include "main/utils.h"
#include "lib/binary_tree.h"
using namespace std;
using TreeNode = BinaryTreeNode;

class Solution {
  public:
    int maxDepth(TreeNode* root) {
      if (!root) {
        return 0;
      }
      int left_depth = maxDepth(root->left);
      int right_depth = maxDepth(root->right);
      return max(left_depth, right_depth) + 1;
    }

    int maxDepth1(TreeNode* root) {
      if (!root) {
        return 0;
      }
      queue<TreeNode*> q;
      q.push(root);
      int ans = 0;
      while (!q.empty()) {
        int cur_len = q.size();
        ++ans;
        while (cur_len) {
          auto node = q.front();
          q.pop();
          if (node->left) {
            q.push(node->left);
          }
          if (node->right) {
            q.push(node->right);
          }
          --cur_len;
        }
      }
      return ans;
    }
};

int main() {
  vector<int> nodes_vec = {1, 2, 3, 4, 5, 6, 7, 8, 9};
  TreeNode* root = CreateBinaryTree(nodes_vec);
  Solution su;
  cout << su.maxDepth(root) << endl;
  cout << su.maxDepth1(root) << endl;
}
